import java.io.*;
import java.net.*;
import java.lang.String;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.GregorianCalendar;
import java.util.PriorityQueue;

public class Client {
	
	public static boolean debug = false;
	private static long start;

    public static void main(String[] pArgs) 
    {
        if(pArgs.length<3)
        {
            //System.out.println("usage: java Client host port boardnum");
            return;
        }

        try
        {
            Socket lSocket = new Socket(pArgs[0],Integer.parseInt(pArgs[1]));
            PrintWriter lOut = new PrintWriter(lSocket.getOutputStream());
            BufferedReader lIn = new BufferedReader(new InputStreamReader(
                                                   lSocket.getInputStream()));

            lOut.println(pArgs[2]);
            lOut.flush();

            String lLine = lIn.readLine();
            ArrayList<String> lines = new ArrayList<String>();

            //System.out.println("Line received: " + lLine);
            //Read number of rows
            int lNumRows = Integer.parseInt(lLine);

            //Read each row
            for(int i = 0; i < lNumRows; ++ i)
            {
            	lLine = lIn.readLine();
                lines.add(lLine);
            }

            // Build the board.
            //lines = easyBoard1();
            
	        Board board = new Board(lines);
//	        System.out.println("Number of fields: " + (board.getElements().length * board.getElements()[0].length));
//	        System.out.println("Number of boxes: " + board.getBoxes().size());
	        
//	        if (debug)
//	        System.out.println(board);
            
            // Solve the board!
            LinkedList<Position> boxes = new LinkedList<Position>();
            boxes.addAll(board.getBoxes()); 

//            GregorianCalendar st = new GregorianCalendar();
            start = (new GregorianCalendar()).getTimeInMillis();
//            System.out.println(board.toString());
            String boxPath = findSolution(board);
//            System.out.println("Time to find solution: " + ((new GregorianCalendar()).getTimeInMillis() - st.getTimeInMillis()) + "msecs");
//
//            
//            System.out.println("Path to get there: " + boxPath);

//            (new SolutionChecker()).recreateSolution(board, boxPath);

            //Send the solution to the server
            lOut.println(boxPath);
            lOut.flush();

            //Read answer from the server
            lLine = lIn.readLine();

            System.out.println(lLine);
        }
        catch(Throwable t)
        {
            t.printStackTrace();
        }
    }

    /**
    * @return a String representation of a simple board
    */
    private static ArrayList<String> easyBoard1()
    {
        ArrayList<String> ret = new ArrayList<String>();
        
//      ret.add("########");
//      ret.add("#     @#");
//      ret.add("# #### #");
//      ret.add("# $..$ #");
//      ret.add("# #### #");
//      ret.add("#      #");
//      ret.add("#      #");
//      ret.add("#      #");
//      ret.add("########");
        
//        ret.add("########");
//        ret.add("#     @#");
//        ret.add("# $###$#");
//        ret.add("# *    #");
//        ret.add("# #### #");
//        ret.add("#  $.# #");
//        ret.add("#  $.#.#");
//        ret.add("#  $.#.#");
//        ret.add("########");
        
        ret.add("########" );
        ret.add("#    @ #" );
        ret.add("# $ $  #" );
        ret.add("#      #" );
        ret.add("### ####" );
        ret.add("#    #.#" );
        ret.add("#   #  #" );
        ret.add("#      #" );
        ret.add("#  ##  #" );
        ret.add("#    #.#" );
        ret.add("#      #" );
        ret.add("########");
        
//		ret.add("###########");
//		ret.add("#  . . .  #");
//		ret.add("# . . . . #");
//		ret.add("#######   #");
//		ret.add("#    $ $  #");
//		ret.add("#       # #");
//		ret.add("###$####  #");
//		ret.add("#@ $   #$ #");
//		ret.add("### $  $  #");
//		ret.add("   ##     #");
//		ret.add("    #######");
        
        return ret;
    }

	private static String findSolution(Board b)
    {
        HashMap<String, Boolean> dp = new HashMap<String, Boolean>();
        PriorityQueue<Node> q = new PriorityQueue<Node>(11, new NodeComparator());

        q.add(new Node(null, "", b));

        while(!q.isEmpty())
        {
        	if((new GregorianCalendar()).getTimeInMillis() - start >= 59000)
        	{
       		System.out.print("TIMED OUT - ");
        		return null;
        	}
//        	System.out.println(q.size());
            Node par = q.poll();
            Board parB = par.getB();
//            System.out.println(parB);
//            if(parB.getElements()[3][5].getCharacter() == BoardElement.EMPTY_FLOOR.getCharacter())
//            {
//            	System.out.println("Board changed");
//            	//System.exit(0);
//            }
            if(debug)
            {
            	System.out.println("Node pulled with weight "+par.getWeight());
                System.out.println(parB);
            }
            
            boolean dontCheck = false;

            //Verify if this board has already a solution
            if(parB.isFinal())
                return par.getPath();

            //Check the DP variable to see if the board extracted has already
            //been tested
            if(dp.containsKey(par.getBs()))
            {
//            	System.out.println("Match found");
                dontCheck = true;
            }
            else
            {
            	dp.put(par.getBs(), true);
            }

            if(dontCheck)
            {
                continue;
            }

            //For each of the boxes of the board, check if they caused a dead
            //configuration or if they are in a tunnel
            for(Position box : parB.getBoxes())
            {
            	boolean deadlock = parB.getDeadlock().isDeadlockFor(parB, box);
                //Check for the deadlock
                if((parB.getElement(box).getCharacter() != BoardElement.BOX_ON_GOAL.getCharacter()) && deadlock)  
                {        
                    dontCheck = true;
                    //System.out.println("Deadlock: \n"+parB);
                    break;
                }
            }

            if(dontCheck)
                continue;
            // Analyze the possible sons
            BoardElement be;
            String pPath, tunnel;
            Position next;
            for(Position box : parB.getBoxes())
            {
            	if (parB.getElement(box).getCharacter() == ' ')
            		System.out.println("Box should be in: "+box);
                //Top
                next = new Position(box.getX() - 1, box.getY());
                be = parB.getElement(next);
                if((be == BoardElement.EMPTY_FLOOR) ||
                   (be == BoardElement.GOAL) ||
                   (be == BoardElement.PLAYER) ||
                   (be == BoardElement.PLAYER_ON_GOAL))
                {
                    pPath = findPath(parB.getPlayerPosition(), 
                                     new Position(box.getX() + 1, box.getY()),
                                     parB);
                    //If the player can get to the correct place to push the
                    //box, proceed
                    if(null != pPath)
                    {
                        String newPath = pPath + 'U';
                        Board sonB = new Board(parB);
                        sonB.commitPath(newPath, 
                                        box,
                                        next
                                       );
                        if(sonB.isInTunnel(next))
                        {
                        	if((tunnel = sonB.commitTunnel(next, false)) != null)
                        		newPath += tunnel;
                        }
                        Node son = new Node(null, par.getPath() + newPath, sonB);
                        son.estimateWeight();
                        q.add(son);
                    }
                }
  
                //Bottom
                next = new Position(box.getX() + 1, box.getY());
                be = parB.getElement(next);
                if((be == BoardElement.EMPTY_FLOOR) ||
                   (be == BoardElement.GOAL) ||
                   (be == BoardElement.PLAYER) ||
                   (be == BoardElement.PLAYER_ON_GOAL))
                {
                    pPath = findPath(parB.getPlayerPosition(), 
                                     new Position(box.getX() - 1, box.getY()),
                                     parB);
                    //If the player can get to the correct place to push the
                    //box, proceed
                    if(null != pPath)
                    {
                        String newPath = pPath + 'D';
                        Board sonB = new Board(parB);
                        sonB.commitPath(newPath, 
                                        box.copy(),
                                        next.copy()
                                       );
                        if(sonB.isInTunnel(next))
                        {
                        	if((tunnel = sonB.commitTunnel(next, true)) != null)
                        		newPath += tunnel;
                        }
                        Node son = new Node(null, par.getPath() + newPath, sonB);
                        son.estimateWeight();
                        q.add(son);
                    }
                }

                //Right
                next = new Position(box.getX(), box.getY() + 1);
                be = parB.getElement(next);
                if((be == BoardElement.EMPTY_FLOOR) ||
                   (be == BoardElement.GOAL)||
                   (be == BoardElement.PLAYER) ||
                   (be == BoardElement.PLAYER_ON_GOAL))
                {
                    pPath = findPath(parB.getPlayerPosition(), 
                                     new Position(box.getX() , box.getY() - 1),
                                     parB);
                    //If the player can get to the correct place to push the
                    //box, proceed
                    if(null != pPath)
                    {
                        String newPath = pPath + 'R';
                        Board sonB = new Board(parB);
                        sonB.commitPath(newPath, 
                                        box.copy(),
                                        next.copy()
                                       );
                        if(sonB.isInTunnel(next))
                        {
                        	if((tunnel = sonB.commitTunnel(next, true)) != null)
                        		newPath += tunnel;
                        }
                        Node son = new Node(null, par.getPath() + newPath, sonB);
                        son.estimateWeight();
                        q.add(son);
                     }
                }

                //Left
                next = new Position(box.getX(), box.getY() - 1);
                be = parB.getElement(next);
                if((be == BoardElement.EMPTY_FLOOR) ||
                   (be == BoardElement.GOAL)||
                   (be == BoardElement.PLAYER) ||
                   (be == BoardElement.PLAYER_ON_GOAL))
                {
                    pPath = findPath(parB.getPlayerPosition(), 
                                     new Position(box.getX(), box.getY() + 1),
                                     parB);
                    //If the player can get to the correct place to push the
                    //box, proceed
                    if(null != pPath)
                    {
                        String newPath = pPath + 'L';
                        Board sonB = new Board(parB);
                        sonB.commitPath(newPath, 
                                        box.copy(),
                                        next.copy()
                                       );
                        if(sonB.isInTunnel(next))
                        {
                        	if((tunnel = sonB.commitTunnel(next, false)) != null)
                        		newPath += tunnel;
                        }
                        Node son = new Node(null, par.getPath() + newPath, sonB);
                        son.estimateWeight();
                        q.add(son);
                     }
                }
            }            
        }

        //No solution was found here, so add the element to the DP variable
        return null;
    }
    /**
    * Method that finds a path for a player to move from p0 to p1 on the given
    * board. It is assumed that p0 is a valid position
    *
    *@param p0 Initial position
    *@param p1 Destination
    *@param b Board where the path should be found
    *
    *@return A string representing the movements that must be made to get from
    *        p0 to p1, or NULL if such path does not exist
    */
    public static String findPath(Position p0, Position p1, Board b)
    {
	//check that the position is reachable
	    if(b.getElement(p1) == BoardElement.WALL ||
	       b.getElement(p1) == BoardElement.BOX ||
	       b.getElement(p1) == BoardElement.BOX_ON_GOAL)
		    return null;

        LinkedList<Node> q = new LinkedList<Node>();
        String newPath;
        BoardElement c;
        Node elem;
        boolean visited[][] = new boolean[b.getNumRows()][b.getNumCols()];
        int x, y;
        Position pos;

        //Place the first element in the queue
        q.push(new Node(p0, "", b));

        //Start the BFS
        while(!q.isEmpty())
        {
            elem = q.poll();
            //If the destination has been found, return.
            if(elem.getP().equals(p1))
                return elem.getPath();

            x = elem.getP().getX();
            y = elem.getP().getY();

            if(visited[x][y])
                continue;

            visited[x][y] = true;
            //Add all valid sons to the queue
            //Top
            if(!visited[x - 1][y])
            {
                pos = new Position(x - 1, y);
                newPath = elem.getPath() + 'U';

                c = b.getElement(pos);
                //Check that the player can move on that position
                if((c == BoardElement.EMPTY_FLOOR) || 
                   (c == BoardElement.GOAL))
                    q.add(new Node(pos, newPath));
            }
            //Bottom
            if(!visited[x + 1][y])
            {
                pos = new Position(x + 1, y);
                newPath = elem.getPath() + 'D';

                c = b.getElement(pos);
                //Check that the player can move on that position
                if((c == BoardElement.EMPTY_FLOOR) || 
                   (c == BoardElement.GOAL) )
                    q.add(new Node(pos, newPath));
            }
            //Right
            if(!visited[x][y + 1])
            {
                pos = new Position(x, y + 1);
                newPath = elem.getPath() + 'R';

                c = b.getElement(pos);
                //Check that the player can move on that position
                if((c == BoardElement.EMPTY_FLOOR) || 
                   (c == BoardElement.GOAL))
                    q.add(new Node(pos, newPath));
            }
            //Left
            if(!visited[x][y - 1])
            {
                pos = new Position(x, y - 1);
                newPath = elem.getPath() + 'L';

                c = b.getElement(pos);
                //Check that the player can move on that position
                if((c == BoardElement.EMPTY_FLOOR) || 
                   (c == BoardElement.GOAL))
                     q.add(new Node(pos, newPath));
            }
        }

        //If got here, the whole map was traversed and no route was found
        return null;
    }

    /**
    * Method that finds the upper left corner reachable by a player starting on p0 on b
    *
    *@param p0 Initial position
    *@param b Board where the path should be found
    *
    *@return A position expressing the desired value
    */
    public static Position findUpperLeftCorner(Position p0, Board b)
    {
        LinkedList<Node> q = new LinkedList<Node>();
        BoardElement c;
        Node elem;
        Position maxP = new Position(b.getNumRows(), b.getNumCols());
        boolean visited[][] = new boolean[b.getNumRows()][b.getNumCols()];
        int x, y;
        BoxComparator comp = new BoxComparator();
        Position pos;

        //Place the first element in the queue
        q.push(new Node(p0));

        //Start the BFS
        while(!q.isEmpty())
        {
            elem = q.poll();
            
            if(comp.compare(elem.getP(), maxP) < 0)
            {
            	maxP = elem.getP().copy();
            	if((maxP.getX() == 1) && (maxP.getY() == 1))
            		break;
            }

            x = elem.getP().getX();
            y = elem.getP().getY();

            if(visited[x][y])
                continue;

            visited[x][y] = true;
            //Add all valid sons to the queue
            //Top
            if(!visited[x - 1][y])
            {
                pos = new Position(x - 1, y);

                c = b.getElement(pos);
                //Check that the player can move on that position
                if((c == BoardElement.EMPTY_FLOOR) || 
                   (c == BoardElement.GOAL))
                    q.add(new Node(pos));
            }
            //Bottom
            if(!visited[x + 1][y])
            {
                pos = new Position(x + 1, y);

                c = b.getElement(pos);
                //Check that the player can move on that position
                if((c == BoardElement.EMPTY_FLOOR) || 
                   (c == BoardElement.GOAL) )
                    q.add(new Node(pos));
            }
            //Right
            if(!visited[x][y + 1])
            {
                pos = new Position(x, y + 1);

                c = b.getElement(pos);
                //Check that the player can move on that position
                if((c == BoardElement.EMPTY_FLOOR) || 
                   (c == BoardElement.GOAL))
                    q.add(new Node(pos));
            }
            //Left
            if(!visited[x][y - 1])
            {
                pos = new Position(x, y - 1);

                c = b.getElement(pos);
                //Check that the player can move on that position
                if((c == BoardElement.EMPTY_FLOOR) || 
                   (c == BoardElement.GOAL))
                     q.add(new Node(pos));
            }
        }

        return maxP;
    }
    
    /**
    * Method that, given a particular board, finds a valid path to push a box
    * located on p0 to p1. It is assumed that p0 is valid on the board
    *
    * @param p0 Box's initial position
    * @param p1 Destination
    * @param b Board where the box should be moved
    * @return A string containing the moves that must be followed in order to
    *         push the box, or NULL if such path does not exist
    */
//    private static String findPathWithBox(Position p0, Position p1, Board b)
//    {
//	    //Check that the position is reachable
//	    if(b.getElement(p1) == BoardElement.WALL ||
//	       b.getElement(p1) == BoardElement.BOX ||
//	       b.getElement(p1) == BoardElement.BOX_ON_GOAL)
//		    return null;
//
//        LinkedList<Node> q = new LinkedList<Node>();
//        boolean visited[][] = new boolean[b.getNumRows()][b.getNumCols()];
//        String newPath, playerPath;
//        BoardElement e;
//        Board eBoard;
//        Node el;
//        int x, y;
//
//        q.push(new Node(p0, "", b));
//
//        while(!q.isEmpty())
//        {
//            el = q.poll();
//
////            System.out.println("Polled node: " + el.getP());
////            System.out.println(el.getB().toString());
//            //Check if this node is the destination
//            if(el.getP().equals(p1))
//                return el.getPath();
//
//
//            x = el.getP().getX();
//            y = el.getP().getY();
//            //Check if the node was already analyzed
//            if(visited[x][y])
//                continue;
//    
//            visited[x][y] = true;
//
//            //Add the sons that are valid moves
//            //Top
//            if(!visited[x - 1][y])
//            {
//                Position nextPos = new Position(x - 1, y);
//                //Check that the box can be pushed on that position
//                e = nextPos.getElement().copy();
//                if((e == BoardElement.EMPTY_FLOOR) || 
//                   (e == BoardElement.GOAL))
//                {
//                    //Find a path for the player to get under the box
//                    playerPath = findPath(el.getB().getPlayerPosition(),
//                                          new Position(x + 1, y), 
//                                          el.getB());
//                    //The player can actually get under the box
//                    if(playerPath != null)
//                    {
//                        newPath = el.getPath() + playerPath + 'U';
//                        eBoard = new Board(el.getB());
//                        eBoard.commitPath(newPath, el.getP().copy(), nextPos.copy());
//                        nextPos.setElement(eBoard.getElement(nextPos).copy());
////                        System.out.println("Pushed node: " + nextPos);
////                        System.out.println(eBoard.toString());
//                        q.add(new Node(nextPos, newPath, eBoard));
//                    }
//                }
//            }
//            //Bottom
//            if(!visited[x + 1][y])
//            {
//                Position nextPos = new Position(x + 1, y, el.getB().getElements()[x + 1][y].copy());
//                //Check that the box can be pushed on that position
//                e = nextPos.getElement().copy();
//                if((e == BoardElement.EMPTY_FLOOR) || 
//                   (e == BoardElement.GOAL))
//                {
//                    //Find a path for the player to get over the box
//                    playerPath = findPath(el.getB().getPlayerPosition(),
//                                          new Position(x - 1, y),
//                                          el.getB());
//                    //The player can actually get over the box
//                    if(playerPath != null)
//                    {
//                        newPath = el.getPath() + playerPath + 'D';
//                        eBoard = new Board(el.getB());
//                        eBoard.commitPath(newPath, el.getP().copy(), nextPos.copy());
//                        nextPos.setElement(eBoard.getElement(nextPos).copy());
// //                       System.out.println("Pushed node: " + nextPos);
// //                       System.out.println(eBoard.toString());
//                        q.add(new Node(nextPos, newPath, eBoard));
//                    }
//                }
//            }
//            //Left
//            if(!visited[x][y - 1])
//            {
//                Position nextPos = new Position(x, y - 1, el.getB().getElements()[x][y - 1].copy());
//                //Check that the box can be pushed on that position
//                e = nextPos.getElement().copy();
//                if((e == BoardElement.EMPTY_FLOOR) || 
//                   (e == BoardElement.GOAL))
//                {
//                    //Find a path for the player to get right to the box
//                    playerPath = findPath(el.getB().getPlayerPosition(), 
//                                          new Position(x, y + 1),
//                                          el.getB());
//                    //The player can actually get under the box
//                    if(playerPath != null)
//                    {
//                        newPath = el.getPath() + playerPath + 'L';
//                        eBoard = new Board(el.getB());
//                        eBoard.commitPath(newPath, el.getP().copy(), nextPos.copy());
//                        nextPos.setElement(eBoard.getElement(nextPos).copy());
////                        System.out.println("Pushed node: " + nextPos);
////                        System.out.println(eBoard.toString());
//                        q.add(new Node(nextPos, newPath, eBoard));
//                    }
//                }
//            }
//            //Right
//            if(!visited[x][y + 1])
//            {
//                Position nextPos = new Position(x, y + 1, el.getB().getElements()[x][y + 1].copy());
//                //Check that the box can be pushed on that position
//                e = nextPos.getElement().copy();
//                if((e == BoardElement.EMPTY_FLOOR) || 
//                   (e == BoardElement.GOAL))
//                {
//                    //Find a path for the player to get left to the box
//                    playerPath = findPath(el.getB().getPlayerPosition(), 
//                                          new Position(x, y - 1),
//                                          el.getB());
//                    //The player can actually get under the box
//                    if(playerPath != null)
//                    {
//                        newPath = el.getPath() + playerPath + 'R';
//                        eBoard = new Board(el.getB());
//                        eBoard.commitPath(newPath, el.getP().copy(), nextPos.copy());
//                        nextPos.setElement(eBoard.getElement(nextPos).copy());
////                        System.out.println("Pushed node: " + nextPos);
////                        System.out.println(eBoard.toString());
//                        q.add(new Node(nextPos, newPath, eBoard));
//                    }
//                }
//            }
//        }
//        return null;
//    }
}
